from typing import List


class Solution:
    def findLength(self, A: List[int], B: List[int]) -> int:
        if not A or not B:
            return 0
        la = len(A)
        lb = len(B)
        # 错误。。。
        # 连续数组，不能进行转移
        # dp = [[0 for j in range(lb)] for i in range(la)]
        # for i in range(len(A)):
        #     for j in range(len(B)):
        #         if A[i] == B[j]:
        #             if i > 0 and j > 0:
        #                 dp[i][j] = dp[i-1][j-1] + 1
        #             else:
        #                 dp[i][j] = 1
        #         if i > 0:
        #             dp[i][j] = max(dp[i][j], dp[i-1][j])
        #         if j > 0:
        #             dp[i][j] = max(dp[i][j], dp[i][j-1])
        # print(dp)
        # return dp[la-1][lb-1]
        ans = 0
        dp = [[0 for j in range(lb)] for i in range(la)]
        for i in range(la):
            for j in range(lb):
                # if A[i] == B[j]:
                #     if i > 0 and j > 0:
                #         dp[i][j] = dp[i-1][j-1] + 1
                #     else:
                #         dp[i][j] = 1
                if A[i] == B[j]:
                    dp[i][j] = 1 + (dp[i-1][j-1] if i and j else 0)
                ans = max(dp[i][j], ans)

        return ans


solve = Solution()

questions = [
    ([1, 2, 3, 2, 1], [3, 2, 1, 4, 7]),
    ([0, 1, 1, 1, 1], [1, 0, 1, 0, 1])
]

for qi, q in enumerate(questions, 1):
    A = q[0]
    B = q[1]
    print(f'#{qi}:', A, B)
    print(f'ans: {solve.findLength(A, B)}')

